1. Field of the Invention
This invention relates to a system memory and allocator for a digital processor which is adapted to evaluate programs represented as binary directed graphs, and more particularly to a processor that evaluates such graphs by progressive substitutions of equivalent graphs.
2. Description of the Prior Art
Most digital computers on the market today are still of the type first postulated by John von Neumann and are sequential in their execution of commands. The first higher-level languages for programming computers, such as FORTRAN and COBOL, reflected this organization, and left with the programmer the responsibilities of storage management and control-flow management, as well as the design of the algorithm to be implemented by the computer. Pure applicative languages, such as pure LISP, differ from imperative languages by relieving the programmer of these management responsibilities.
An alternative to pure LISP is the Saint Andrews Static Language, or SASL, which was developed by David A. Turner (SASL Language Manual, University of St. Andrews, 1976). By introducing a number of constants called "combinators", this language may be transformed into a variable-free notation (D. A. Turner, "A New Implementation Technique for Applicative Languages", Software--Practice and Experience, Vol. 9, pp. 31-49, 1979). This notation is particularly advantageous for handling higher-order functions (which may take functions as arguments and return functions as results) and non-strict functions (which may return a result even if one or more arguments are undefined).
The implementation technique developed by Turner employs a set of primitive functions such as plus, minus, and so forth, and a set of combinators, which are higherorder non-strict functions. These operators are formally defined by substitution rules, some examples of which are
______________________________________ S f g x = f x (g x) K x y = x I x = x Y h = h (Y h) C f x y = f y x B f g x = f (g x) cond p x y = x , if p is true y , if p is false plus m n = r , where m and n must already have been reduced to numbers and r is the sum of m and n ______________________________________
Other combinators and their definitions are to be found in the above referenced Turner publication.
This combinator notation may be conveniently represented as a binary directed graph in which each node represents the application of a function to an argument. (These graphs are known as SK-graphs from the names of the first two combinators.) The substitution rules may then be interpreted as graph transformation rules, and these graphs (and, therefore, the programs they represent) may be evaluated, in a process known as reduction, by a processor of a fairly simple nature. Such a reduction processor is disclosed in the Bolton et al. U.S. Pat. No. 4,447,875, entitled "Reduction Processor for Executing Programs Stored as Treelike Graphs Employing Variable-Free Applicative Language Codes".
Details of the reduction process can be found in the Turner paper, but a brief example is helpful. FIGS. 1A-D illustrate the reduction of a graph representing the SASL program.
______________________________________ successor 2 WHERE successor x = 1 + x ______________________________________
This program is translated (compiled) into the combinator expression EQU C I 2 (plus 1)
that is represented by the graph in FIG. 1A. Successive transformations of this graph yield
______________________________________ I (plus 1) 2 using the C rule (FIG. 1B) plus 1 2 using the I rule (FIG. 1C) 3 using the plus rule (FIG. 1D) ______________________________________
The substitutions performed to reduce a graph require the manipulation of a number of different pieces of data, such as pointers and combinator codes, which are shifted from one location to another in a register file. In the embodiment disclosed in the above referenced Bolton et al. application, each graph-reduction step required a sequence of register-file transfers. In many cases, however, the required transfers between registers could be performed simultaneously, with a consequent increase in speed.
After performing one of these transformations, the processor must traverse the graph in search of the next transformation site (called a "redex"). During this search nodes are examined and a variety of tests are performed, such as determining whether the left side of a node represents a pointer or a combinator. Again, in the machine described in the Bolton et al. application, these tests must be made sequentially: in many cases, though, these tests could be performed simultaneously.
It is then an object of the present invention to provide an improved processing system for the evaluation of binary directed graphs through a series of substitutions.
It is another object of the present invention to provide such a processor wherein each substitution can be accomplished faster by a number of simultaneous register transfers.
It is still a further object of the present invention to provide an allocator and system memory for such a reduction processor where the allocator selects addresses of new nodes for transfer to the reduction processor for use in evaluating the respective graphs.